/*

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

 

示例：

输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/target-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

/*
解法 一:
一  回溯算法
但是没有剪枝，更像是一个暴力算法
*/

class Solution {
public:
    int target = 0;
    int res = 0;
    void findTargetSumWaysHelper(int index ,int &target,vector<int>& nums, int S)
    {
        if(target == S && index ==  nums.size() )
            res ++ ;

        if(index >= nums.size())
            return;
        
        target += nums[index];
        findTargetSumWaysHelper( index +1,target, nums,  S);

        target -= 2*nums[index];
        findTargetSumWaysHelper( index +1,target, nums,  S);

        target += nums[index];

    }
    int findTargetSumWays(vector<int>& nums, int S) 
    {
        findTargetSumWaysHelper(0, target, nums,  S);
        return res;
    }
};


/*
解法 二:
 动态规划
*/

class Solution {
public:
    int target = 0;
    int res = 0;
    vector< vecotr<int> > table;
    vector<int> sum_aray;
    int get_tablevalue(int i,int j)
    {
        if (j > sum_aray[i] && -j > sum_aray[i])
        {
            return 0;
        }
        else
        {
            return table[i][j];
        }
    }
    int findTargetSumWays(vector<int>& nums, int S) 
    {
      
       int sum = 0; 
       for(int i =0; i<=nums.size();i++)
       {
           sum += nums[i];
           sum_aray.push_back(sum);
       } 

       
       for(int i =0 ;i<nums.size();i++)
       {
           table.push_back(vecotr<int>(2()sum_aray[i]+1,0));
       }

       table[0][-nums[0]] = 1;
       table[0][nums[0]] = 1;

       for(int i =1;i<nums.size();i++)
       {
           for (int j= -sum_aray[i];j<=sum_aray[i];j++)
           {
               table[i][j] = get_tablevalue(i-1,j-nums[i]) + get_tablevalue(i-1,j+nums[i]);
           }
           
       }
       return table[i][S];
    }
};